package leetcodehot100;

import com.sun.source.tree.Tree;

import javax.lang.model.type.IntersectionType;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.IntFunction;
import java.util.stream.Collectors;

public class Test {
    public static void main(String[] args) {
//        new HashMap<>();
//        new ArrayList<>();
//        new Hashtable<>();
//
//        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
//        list.add(null);
//        Integer integer = list.get(0);
//        System.out.println(integer);
//
//        Map<String, Integer> map = new ConcurrentHashMap<>();
//        map.put("1", null);
//        Integer integer1 = map.get("1");
//        System.out.println(integer1);
//
//        String test = "hello";
//        char[] chars = test.toCharArray();
//        Set<Integer> set = new HashSet<>();
//        Set<Integer> set2 = new HashSet<>(set);

//        List<Integer> list2 = new ArrayList<>();
//        list2.add(1);
//        list2.add(1);
//        list2.add(1);
//        list2.add(2);
//        list2.add(2);
//        System.out.println(list2);
//        list2.remove((Integer)2);
//        System.out.println(list2);

        // 二维数组排序
        int[][] arr = {{5, 1}, {3, 2}, {4, 1}};
        Arrays.sort(arr, ((o1, o2) -> o2[0] - o1[0]));
        for (int[] ints : arr) {
            System.out.println(Arrays.toString(ints));
        }
        // 一维数组可以使用Arrays.sort降序吗？
        int[] a = {5, 3, 2, 6, 1};
        // Arrays.stream 只适应于 int 、long、 double
        Integer[] toArray = Arrays.stream(a).boxed().toArray(Integer[]::new);
        Arrays.sort(toArray, ((o1, o2) -> o2 - o1));
        System.out.println(Arrays.toString(toArray));

    }

    /**
     * 字母异位词分组
     *
     * @param strs
     * @return
     */
    private static List<List<String>> test(String[] strs) {
        return Arrays.stream(strs).collect(Collectors.groupingBy(s -> {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            return new String(arr);
        })).entrySet().stream().map(x -> x.getValue()).collect(Collectors.toList());
    }

    /**
     * 最长连续序列
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        // 有时需要将原始类型转换为盒式类型。
        // boxed()的作用就是将基本（原始）类型的stream转成了包装（boxed）类型的Stream
        // 例如：上述方法实现的是int类型的stream转成了Integer类型的Stream
        Set<Integer> collect = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        int res = 1;
        for (Integer x : collect) {
            if (!collect.contains(x - 1)) {
                // 不包含前一个值
                int count = 1;
                int curNum = x;
                while (collect.contains(curNum + 1)) {
                    curNum++;
                    count++;
                }
                res = Math.max(count, res);
            }
        }
        return res;
    }

    /**
     * 移动0
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        // 双指针
        int s1 = 0;
        int s2 = 1;
        while (s2 < nums.length) {
            if (nums[s2] != 0) {
                int tmp = nums[s2];
                nums[s2] = nums[s1];
                nums[s1] = tmp;
                s1++;
            }
            s2++;
        }
    }

    /**
     * 最大容量
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;

        int max = 0;
        while (left < right) {
            int area = (height[left] < height[right] ? height[left] : height[right]) * (right - left);
            if (area > max) {
                max = area;
            }
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return max;
    }

    /**
     * 两数字和
     */
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int iWant = target - nums[i];
            if (map.containsKey(iWant)) {
                res[0] = i;
                res[1] = map.get(iWant);
                break;
            }
            map.put(nums[i], i);
        }
        return res;
    }

    /**
     * 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 1.排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // 修改为双指针寻找两数之和（O(n^2)）
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            int twoSum = (-1) * nums[i];
            while (left < right) {
                if (nums[left] + nums[right] == twoSum) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    // 这个步骤很关键
                    left++;
                    right--;
                    // 去重
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                } else if (nums[left] + nums[right] < twoSum) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return res;
    }

    /**
     * 无重复字符的最长子串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int maxLen = 1;
        // 定义窗口
        Set<Character> window = new HashSet<>();
        // 初始化窗口
        window.add(s.charAt(0));
        // 移动窗口遍历
        int left = 0;
        int right = 1;
        while (left < s.length()) {
            // 右边元素左移
            while (right < s.length() && !window.contains(s.charAt(right))) {
                window.add(s.charAt(right));
                right++;
            }
            // 更新
            maxLen = Math.max(maxLen, window.size());
            // 左边元素右移
            window.remove(s.charAt(left));
            left++;
        }
        return maxLen;
    }

    /**
     * 找到字符串中所有字母异位词
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        // 思路遍历+窗口
        int sLen = s.length();
        int pLen = p.length();
        // s < p不存在
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        // 其他情况
        List<Integer> res = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        // 初始化第一个窗口
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            res.add(0);
        }
        // 判断其他窗口
        for (int i = 0; i < sLen - pLen; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + pLen) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                res.add(i + 1);
            }
        }
        return res;
    }

    /**
     * 和为 K 的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        // 前缀和 + hash 实现 O(N) 的时间复杂度
        // 和为k的子数组[i,j]转换为前缀和：sum[i] - sum[j-1] == k
        // 所以遍历到i的时候只需要找到前面有几个和为 sum[i] - k 的元素即可
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int preSum = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum - k)) {
                res += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return res;
    }

    /**
     * 滑动窗口最大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        // 规律：如果窗口内后面的元素大于前面的，那么在他出窗口之前，前面的元素都没有用了
        // 当然后面该入窗口入窗口
        Deque<Integer> window = new LinkedList<>();
        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            while (!window.isEmpty() && nums[i] > nums[window.peekLast()]) {
                window.pollLast();
            }
            window.addLast(i);
        }
        // 遍历寻找最大值
        int index = 0;
        for (int i = k; i < nums.length; i++) {
            // 添加到结果集
            res[index++] = nums[window.peekFirst()];
            // 移动窗口
            while (!window.isEmpty() && window.peekFirst() < i - k + 1) {
                window.pollFirst();
            }
            while (!window.isEmpty() && nums[i] > nums[window.peekLast()]) {
                window.pollLast();
            }
            window.addLast(i);
        }
        res[index] = nums[window.peekFirst()];
        return res;
    }

    /**
     * 最大子数组和
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        // 经典动态规划
        // dp[i] 表示以 i 未结尾的最大子数组和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] + dp[i - 1] < nums[i]) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;

    }

    /**
     * 合并区间
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        // 遍历
        int row = intervals.length;
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < row - 1; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if (res.isEmpty() || res.get(res.size() - 1)[1] < start) {
                res.add(new int[]{start, end});
            } else {
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], end);
            }
        }
        int[][] ints = res.toArray(int[][]::new);
        return ints;
    }

    public void rotate(int[] nums, int k) {
        int len = nums.length;
        // 1.反转整个数组
        reverse(nums, 0, len - 1);

        // 2.反转前 0-k%nums.length-1 个
        reverse(nums, 0, k % len - 1);

        // 3.反转 k%nums.length-nums.length 个
        reverse(nums, k % len, len - 1);

    }

    /**
     * 轮转数组
     *
     * @param arr
     * @param start
     * @param end
     */
    private void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

    /**
     * 除自身以外数组的乘积
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] leftMulti = new int[len];
        int[] rightMulti = new int[len];

        leftMulti[0] = 1;
        rightMulti[len - 1] = 1;
        // leftMulti[i] | rightMulti[i] 表示以 i 结尾的左右元素的乘积
        for (int i = 1; i < len; i++) {
            leftMulti[i] = nums[i - 1] * leftMulti[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            rightMulti[i] = nums[i + 1] * rightMulti[i + 1];
        }
        // 遍历
        int[] res = new int[len];
        for (int i = 0; i < len; i++) {
            res[i] = leftMulti[i] * rightMulti[i];
        }
        return res;
    }

    /**
     * 缺失的第一个正数
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        // 最开始想到的方法
        Set<Integer> set = Arrays.stream(nums).boxed().filter(x -> x > 0).collect(Collectors.toSet());
        for (int i = 1; i <= nums.length; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return nums.length + 1;

        // 思路：原地哈希（关键在于标记过的元素不重复标记）
        // 1. 我们将数组中所有小于等于 0 的数修改为 N+1；
        // 2. 我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；
        // 3. 在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。
        // // 1.记录最大值
        // int max = nums.length;

        // // 2.替换
        // for (int i = 0; i < max; i ++) {
        //     if (nums[i] <= 0) {
        //         nums[i] = max + 1;
        //     }
        // }

        // // 3.标记
        // for (int i = 0; i < max; i ++) {
        //     if (Math.abs(nums[i]) <= max) {
        //         int index = Math.abs(nums[i]) - 1;
        //         nums[index] *= (nums[index] > 0 ? -1 : 1);
        //     }
        // }

        // // 4.收集
        // for (int k = 0; k < max; k ++) {
        //     if (nums[k] > 0) {
        //         return k+1;
        //     }
        // }

        // return max + 1;
    }

    /**
     * 原来二分查找还能这样写
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (target <= nums[0]) {
            return 0;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 搜索二维矩阵（前提整体有序）
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 最优解，一次二分查找（下标映射）
        // 给定一个 mid 和 row 、col 如何确定在二维数组中的下标？
        // 1,2,3
        // 4,5,6
        // 7,8,9
        // mid = 4 --> (x,y)==(4/col,4%col)==(1,1)
        int col = matrix[0].length;

        int left = 0;
        int right = matrix[0].length * matrix.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;

            if (matrix[mid / col][mid % col] < target) {
                left = mid + 1;
            } else if (matrix[mid / col][mid % col] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        return false;

        // 方式二：z字形搜索
        // int row = matrix.length;
        // int i = 0;
        // int j = matrix[0].length - 1;
        // // 不断缩小target的可能范围
        // while (i < row && j >= 0) {
        //     if (matrix[i][j] < target) {
        //         i ++;
        //     } else if (matrix[i][j] > target) {
        //         j --;
        //     } else {
        //         return true;
        //     }
        // }
        // return false;

        /**
         * 找到链表交点 notable 重要的，显著的  plausible 似乎合理的，似乎可信 tentiative 不确定的 sensible 明智的
         */
//        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//            ListNode h1 = headA;
//            ListNode h2 = headB;
//            while (h1 != h2) {
//                h1 = h1 == null ? headB : h1.next;
//                h2 = h2 == null ? headA : h2.next;
//            }
//            return h1;
//        }

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode();
        ListNode pre = res;

        if (lists.length == 0) {
            return res;
        }
        // 1. 借助优先级队列，以每个链表的头结点的 value 为排序字段
        PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> {
            return o1.val - o2.val;
        });
        for (ListNode list : lists) {
            queue.offer(list);
        }
        // 2. 循环出队列，直到为空，每出一次删除一个元素，如果list的size为0则删除当前list
        while (!queue.isEmpty()) {
            ListNode list = queue.peek();
            pre.next = list;
            pre = pre.next;

            list = list.next;
            queue.poll();
            if (list != null) {
                queue.offer(list);
            }
        }
        return res.next;
    }

    /**
     * 寻找第 k 大
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        // 1.建堆 , 大根堆O(n)
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            // 向下调整建堆
            shiftDown(nums, i, nums.length);
        }

        // 2.做 k - 1 次删除
        int i = 1;
        while (i < k) {
            int tmp = nums[0];
            nums[0] = nums[nums.length - i];
            nums[nums.length - i] = tmp;

            shiftDown(nums, 0, nums.length - i);
            i++;
        }
        // 3.返回堆顶元素
        return nums[0];
    }

    private void shiftDown(int[] nums, int parent, int len) {
        // 找到孩子结点
        int child = 2 * parent + 1;
        while (child < len) {
            if (child + 1 < len && nums[child + 1] > nums[child]) {
                child++;
            }
            if (nums[child] > nums[parent]) {
                // 交换
                int tmp = nums[child];
                nums[child] = nums[parent];
                nums[parent] = tmp;
                // 继续向下交换
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 搜索旋转排序数组
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        // 1.利用局部有序性
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先判断分割后哪一个部分是有序的
            if (nums[left] <= nums[mid]) {
                // 左边有序
                if (target >= nums[left] && target < nums[mid]) {
                    // target 在有序范围内
                    right = mid - 1;
                } else {
                    // target 不在有序范围内
                    left = mid + 1;
                }
            } else {
                // 右边有序
                if (target > nums[mid] && target <= nums[right]) {
                    // target 在有序范围内
                    left = mid + 1;
                } else {
                    // target 不在有序范围内
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 旋转数组最小数字
     *
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        // 使用二分
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[right]) {
                // 最小值在右边（旋转过去的数字）, 去右边找
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // 最小值在左边，去左边找
                right = mid;
            } else {
                // 相等，如果数组中有重复元素，此时不能确定，只能紧缩区间
                right--;
            }
        }
        return nums[left];
    }

    /**
     * 找到中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // todo
        return 1.0;
    }

    int[] array;
    int usedSize;


    /**
     * 数据流的中位数
     *
     * @param num
     */
    // 维护两个堆，左堆是大根堆, 堆顶表示小于中位数的最大值
    Queue<Integer> queueLeft = new PriorityQueue<>((o1, o2) -> o2 - o1);
    // 右堆是小根堆，堆顶表示大于中位数的最小值
    Queue<Integer> queueRight = new PriorityQueue<>((o1, o2) -> o2 - o1);

    public void addNum(int num) {
        if (queueLeft.isEmpty() || num <= queueLeft.peek()) {
            // 1.当 queueLeft 为空的时候，或者新添加的数小于等于 queueLeft 的堆顶元素的时候, 添加到 left
            queueLeft.offer(num);
            // 1.1 元素数量发生变化，中位数也可能变化，所以需要挪动元素
            if (queueLeft.size() - 1 > queueRight.size()) {
                queueRight.offer(queueLeft.poll());
            }
        } else {
            // 2.否则添加到 right 中
            queueRight.offer(num);
            // 2.1 元素数量发生变化，中位数也可能变化，所以需要挪动元素
            if (queueRight.size() > queueLeft.size()) {
                queueLeft.offer(queueRight.poll());
            }
        }
    }

    public double findMedian() {
        int size = queueLeft.size() + queueRight.size();
        if (size % 2 == 0) {
            // 总数为偶数个
            return queueLeft.peek();
        } else {
            // 总数为奇数个
            return (queueLeft.peek() + queueRight.peek()) / 2.0;
        }
    }

    /**
     * 螺旋矩阵
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // 四个指针转圈圈
        int row = matrix.length;
        int col = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int left = 0;
        int right = col - 1;
        int top = 0;
        int bottom = row - 1;
        while (left <= right && top <= bottom) {
            // 右
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++;
            // 下
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;
            // 左
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
            }
            bottom--;
            // 上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
            }
            left++;
        }
        return res;
    }
    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
    }
    public int kthSmallest(TreeNode root, int k) {
        // helper(root);
        // return res.get(k-1);
        Deque<TreeNode> stack = new LinkedList<>();
        // 使用栈代替递归遍历，可以起到更灵活的控制（找到结果就可以停止）
        while (!stack.isEmpty() || root != null) {
            // root 不为空
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 出栈
            root = stack.pop();
            k --;
            if (k == 0) {
                break;
            }
            root = root.right;
        }
        return root.val;
    }

    /**
     * 有效括号生成
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 递归
        getResult(n, n, res, new StringBuilder());
        return res;
    }

    private void getResult(int left, int right, List<String> res, StringBuilder current) {
        if (left == 0 && right == 0) {
            res.add(current.toString());
            return;
        }
        if ((left != 0 || right != 0) && left <= right) {
            if (left != 0) {
                left --;
                current.append("(");
                getResult(left, right, res, current);
                current.deleteCharAt(current.length() - 1);
                left ++;
            }
            if (right != 0) {
                right --;
                current.append(")");
                getResult(left, right, res, current);
                current.deleteCharAt(current.length() - 1);
                right ++;
            }
        }
    }

    /**
     * 分割回文串
     */
    List<List<String>> res;
    List<String> tmp;
    String str;
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        tmp = new ArrayList<>();
        this.str = s;
        // 递归回溯
        dfs(0);
        return res;
    }

    private void dfs(int begin) {
        // 终止条件
        if (begin == str.length()) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        // 遍历
        for (int i = begin; i < str.length(); i ++) {
            String src = str.substring(begin,i+1);
            if (!check(src)) {
                continue;
            }
            tmp.add(src);
            dfs(i+1);
            tmp.remove(tmp.size() - 1);
        }
    }

    private boolean check(String str) {
        int start = 0;
        int end = str.length()-1;
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start ++;
            end --;
        }
        return true;
    }

    /**
     * 买股票的最佳时机-最简单的贪心
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        // 贪心：想象如果我在史低买入就好了，
        // 那么我只需要考虑史低之后每天能卖多少钱
        int minVal = Integer.MAX_VALUE; // 记录史低
        int profit = 0; // 记录利润
        for (int i = 0; i < prices.length; i ++) {
            if (prices[i] < minVal) {
                minVal = prices[i];
            } else {
                profit = Math.max(prices[i] - minVal, profit);
            }
        }
        return profit;
    }

    /**
     * 划分字母区间
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        // 找到每个字符出现的最后一个位置，维护 maxEnd
        int[] lastIndex = new int[26];
        for (int i = 0; i < s.length(); i ++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int end = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < s.length(); i ++) {
            // 维护最大 end
            end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
            if (end == i) {
                // 当前片段找完了
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }

    /**
     * 连续最大乘积（前后遍历--技巧）
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        // dp[i] 表示以 i 结尾的连续最大乘积结果
        int[] dp = new int[nums.length + 1];
        dp[0] = 1;
        int res = nums[0];
        // 2 3 -1 -2 3
        int product = 1;
        for (int i = 0; i < nums.length; i++) {
            product *= nums[i];
            res = Math.max(res, product);
            if (nums[i] == 0) {
                product = 1;
            }
        }

        product = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            product *= nums[i];
            res = Math.max(res, product);
            if (nums[i] == 0) {
                product = 1;
            }
        }

        return res;
    }

    /**
     * 正常解法--动态规划
     * @param nums
     * @return
     */
    public int maxProduct2(int[] nums) {
        // 这道题的关键是存在负数，所以所以需要维护两个dp
        int[] minDp = new int[nums.length];
        int[] maxDp = new int[nums.length];
        minDp[0] = nums[0];
        maxDp[0] = nums[0];

        int res = Integer.MIN_VALUE;

        for (int i = 1; i < nums.length; i ++) {
            maxDp[i] = Math.max(maxDp[i-1]*nums[i],Math.max(nums[i],minDp[i-1]*nums[i]));
            minDp[i] = Math.min(minDp[i-1]*nums[i],Math.min(nums[i],maxDp[i-1]*nums[i]));
            res = Math.max(res,maxDp[i]);
        }

        return res;
    }
}


